__author__ = 'st316'
'''
Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.

Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

Someone says dfs
'''


class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        mapper = {'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl', '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz',
                  '0': ' '}
        s = []
        for c in digits:
            s.append(mapper[c])
        return self.permutation(s)

    def permutation(self, s):
        l = len(s)
        r = []
        if l == 0:
            return ['']
        if l == 1:
            r.extend([c for c in s[0]])
        else:
            for c in s[-1]:
                r.extend([x + c for x in self.permutation(s[:-1])])
        return r


if __name__ == '__main__':
    s = Solution()
    print s.letterCombinations('23')
